/*
 * @lc app=leetcode.cn id=481 lang=typescript
 *
 * [481] 神奇字符串
 */

// @lc code=start
function magicalString(n: number): number {
  if (n < 4) return 1;
  // 构建初始状态：122
  const s: number[] = new Array(n).fill(0).map((_, i) => {
    if (i === 0) return 1;
    else if (i === 1 || i === 2) return 2;
    else return 0;
  });

  let ans = 1;
  // s[i]，每组的数字出现几次
  let i = 2;
  // s[j]，每组的数字是什么
  let j = 3;
  while (j < n) {
    let size = s[i];
    const num = 3 - s[j - 1];
    while (j < n && size) {
      if (num === 1) ans++;
      s[j++] = num;
      size--;
    }
    i++;
  }

  return ans;
}
// @lc code=end
